package biolabs.space;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import biolabs.util.Pair;

/**
 * Represents the shape of grid objects as an enumeration of grid elements.
 * @param <P> is a type that defines a position in the grid,
 * such as {@link Discrete2DPosition} or {@link Discrete3DPosition}.
 */
public class GridShape<P extends  DiscretePosition<P,C>, C extends ContinuousPosition<C,P>> {

	private Set<P> shape;			 // set of all elements of this shape
	transient private Set<P> border; // set of border elements
	transient private C cog;		 // center of gravity

	/**
	 * Constructs the shape from the given set of grid elements.
	 * @param gridElements collection of grid elements the new
	 *   shape will contain. Must be non-empty.
	 * @throws IllegalArgumentException if {@code gridElements} is empty.
	 */
	public GridShape(Collection<P> gridElements){
		if(gridElements.isEmpty())
			throw new IllegalArgumentException("Non-empty collection required");
		shape = new HashSet<P>(gridElements);
		border = new HashSet<P>();
		recomputeBorder();
	}

	/**
	 * Constructs the shape from the given grid elements.
	 * @param gridElements grid elements the new shape will contain.
	 *   At least one must be provided.
	 * @throws IllegalArgumentException if no argument is provided.
	 */
	public GridShape(P... gridElements) {
		this(Arrays.asList(gridElements));
	}

	/**
	 * Creates a copy of {@code s}.
	 */
	public GridShape(GridShape<P, C> s){
		shape = new HashSet<P>(s.shape);
		border = new HashSet<P>(s.border);
		cog = s.cog;
	}

	/**
	 * Returns this shape's center of gravity, which is
	 * the arithmetic mean of all contained grid elements.
	 */
	public C getCenterOfGravity(){
		if(cog == null)
			recomputeCenterOfGravity();
		return cog;
	}

	/**
	 * Returns the number of grid elements occupied by this shape.
	 */
	public int getVolume(){
		return shape.size();
	}

	/**
	 * Adds the given grid element to this shape.
	 * @param e The grid element that will be added to this shape.
	 * @return {@code true} if {@code e} was added to this shape,
	 *   {@code false} if {@code e} was already there.
	 */
	public boolean addElement(P e){
		if(!shape.add(e))
			return false;
		if(isAtBorder(e))
			border.add(e);
		for(P n: e.getNeighbors())
			if(!isAtBorder(n))
				border.remove(n);
		cog = null;
		return true;
	}

	/**
	 * Adds the given grid elements to this shape.
	 * @param col The grid elements that will be added to this shape.
	 */
	public void addElements(Collection<P> col) {
		shape.addAll(col);
		recomputeBorder();
		cog = null;
	}

	/**
	 * Removes the given grid element from this shape.
	 * @param e grid element that will be removed.
	 * @return {@code true} if {@code e} was removed from
	 *   this shape, {@code false} if it was not there.
	 * @throws IllegalStateException if {@code e} is the only element
	 *   of this shape. In this case, {@code e} is not removed.
	 */
	public boolean removeElement(P e){
		if(shape.size()==1 && shape.contains(e))
			throw new IllegalStateException("Trying to remove the last element of the shape");
		if(!shape.remove(e))
			return false;
		border.remove(e);
		List<P> n = e.getNeighbors();
		n.retainAll(shape);
		border.addAll(n);
		cog = null;
		return true;
	}

	/**
	 * Removes the given grid elements from this shape.
	 * @param col a collection of elements that will be removed.
	 * @throws IllegalStateException if the size of {@code col}
	 * is greater than or equal to the size of this shape.
	 * In this case, no element is removed from the shape.
	 */
	public void removeElements(Collection<P> col) {
		if(shape.size() <= col.size())
			throw new IllegalStateException("Trying to remove all elements of the shape");
		shape.removeAll(col);
		border.removeAll(col);
		for(P e: col) {
			List<P> ns = e.getNeighbors();
			for(P n: ns) {
				if(shape.contains(n))
					border.add(n);
			}
		}
		cog = null;
	}

	/**
	 * Returns the description of the minimal
	 * rectangular frame which this shape fits in.
	 * @return a pair {@code p} where {@code p.a} is the origin
	 * of the frame and {@code p.b} contains frame's dimensions.
	 */
	public Pair<P, P> getSpan(){
		assert !shape.isEmpty();
		Iterator<P> i = shape.iterator();
		P min, max;
		min = max = i.next();
		while(i.hasNext()){
			P p = i.next();
			min = min.mapMin(p);
			max = max.mapMax(p);
		}
		P dims = max.plus(max.one()).minus(min);
		return new Pair<P, P>(min, dims);
	}

	/**
	 * Translates this shape by the given move.
	 */
	public void translate(P move) {
		Set<P> newShape = new HashSet<P>(shape.size());
		Set<P> newBorder = new HashSet<P>(border.size());
		for(P p: shape)
			newShape.add(p.plus(move));
		for(P p: border)
			newBorder.add(p.plus(move));
		shape = newShape;
		border = newBorder;
		if(cog != null)
			cog = cog.plus(move.continuous());
	}

	/**
	 * Returns a new shape that is a translation
	 * of this shape by the given move.
	 */
	public GridShape<P, C> translated(P move) {
		List<P> newShape = new ArrayList<P>(shape.size());
		for(P p: shape)
			newShape.add(p.plus(move));
		return new GridShape<P, C>(newShape);
	}

	/**
	 * Returns a set of elements occupied by this shape.
	 *
	 * The returned set is an unmodifiable view of this shape's elements.
	 * Any changes to this shape are visible through the returned set.
	 */
	public Set<P> getElements(){
		return Collections.unmodifiableSet(shape);
	}

	/**
	 * Returns this shape's border elements. A border element is an element
	 * of this shape that has a neighbor which is not in this shape.
	 *
	 * The returned set is an unmodifiable view of border elements. Any
	 * changes to this shape's border are visible through the returned set.
	 */
	public Set<P> getBorderElements(){
		return Collections.unmodifiableSet(border);
	}

	/**
	 * Returns the set of grid elements immediately outside
	 * this shape. That is the set of elements that are not
	 * in this shape and have a neighbor inside this shape.
	 */
	public Set<P> getOuterBorder(){
		Set<P> s = new HashSet<P>();
		for(P p: border)
			for(P n: p.getNeighbors())
				if(!shape.contains(n))
					s.add(n);
		return s;
	}

	private void recomputeBorder(){
		border.clear();
		for(P p: shape)
			if(isAtBorder(p))
				border.add(p);
	}

	private void recomputeCenterOfGravity(){
		cog = computeCenterOfGravity();
	}

	private C computeCenterOfGravity(){
		if(shape.isEmpty())
			throw new IllegalArgumentException("Trying to compute" +
					" the center of gravity of an empty shape");

		Iterator<P> i = shape.iterator();

		P c = i.next();
		while(i.hasNext())
			c = c.plus(i.next());

		return c.continuous().divide(shape.size());
	}

	/**
	 * Returns {@code true} if {@code p} is at the border of this shape, {@code false} otherwise.
	 * An element is at the border if it has a neighbor that is not part of the shape.
	 */
	private boolean isAtBorder(P p){
		for(P q: p.getNeighbors())
			if(!shape.contains(q))
				return true;
		return false;
	}

}
